import java.util.ArrayList;
import java.util.List;

public class KnightTour {
    private static final int[][] MOVES = {
        {2, 1}, {1, 2}, {-1, 2}, {-2, 1},
        {-2, -1}, {-1, -2}, {1, -2}, {2, -1}
    };
    
    private int m;
    private int n;
    private int[][] board;
    private List<List<int[]>> successfulPaths;
    private int successfulPathCount;

    public KnightTour(int m, int n) {
        this.m = m;
        this.n = n;
        this.board = new int[m][n];
        this.successfulPaths = new ArrayList<>();
        this.successfulPathCount = 0;
    }

    public void findPaths(int startX, int startY, int targetX, int targetY) {
        List<int[]> currentPath = new ArrayList<>();
        currentPath.add(new int[]{startX, startY});
        board[startX][startY] = 1;
        
        backtrack(startX, startY, targetX, targetY, currentPath);
        
        System.out.println("Total successful paths: " + successfulPathCount);
        for (List<int[]> path : successfulPaths) {
            printPath(path);
        }
    }

    private void backtrack(int x, int y, int targetX, int targetY, List<int[]> currentPath) {
        if (x == targetX && y == targetY) {
            successfulPathCount++;
            successfulPaths.add(new ArrayList<>(currentPath));
            return;
        }

        for (int[] move : MOVES) {
            int nextX = x + move[0];
            int nextY = y + move[1];
            
            if (isValid(nextX, nextY) && board[nextX][nextY] == 0) {
                board[nextX][nextY] = 1;
                currentPath.add(new int[]{nextX, nextY});
                
                backtrack(nextX, nextY, targetX, targetY, currentPath);
                
                board[nextX][nextY] = 0;
                currentPath.remove(currentPath.size() - 1);
            }
        }
    }

    private boolean isValid(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    private void printPath(List<int[]> path) {
        System.out.print("Path: ");
        for (int[] pos : path) {
            System.out.print("(" + pos[0] + "," + pos[1] + ") ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int m = 5; // 棋盘行数
        int n = 5; // 棋盘列数
        int startX = 0; // 起始位置x
        int startY = 0; // 起始位置y
        int targetX = 4; // 目标位置x
        int targetY = 4; // 目标位置y
        
        KnightTour knightTour = new KnightTour(m, n);
        knightTour.findPaths(startX, startY, targetX, targetY);
    }
}